package william.tree;

/**
 * @author ZhangShenao
 * @date 2024/3/14
 * @description <a href="https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 */
public class Leetcode236_二叉树的最近公共祖先 {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    /**
     * 采用递归实现
     * p和q的最近公共祖先,只会存在以下3种情况:
     * - p和q分别存在在root的左、右子树中,此时root为最近公共祖先
     * - p是q的祖先,q在p的左子树或右子树中,此时p为最近公共祖先
     * - q是p的祖先,p在q的左子树或右子树中,此时q为最近公共祖先
     * 按照dfs对树进行深度优先遍历,直到找到节点p或节点q
     * <p>
     * 时间复杂度O(N) 对树进行一次遍历
     * 空间复杂度O(N) 递归栈深度
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //边界条件校验
        if (root == null || p == null || q == null) {
            return null;
        }

        //如果当前根节点就是p或q节点,则当前节点就是最近公共祖先,直接返回当前节点
        if (root == p || root == q) {
            return root;
        }

        //递归在左、右子树中分别查找p和q
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        //如果在左、右子树中都找到了q或q,说明p、q两个节点分别在左、右子树上,则当前节点就是最近公共祖先,直接返回当前节点
        if (left != null && right != null) {
            return root;
        }

        //剩余情况:p、q同时在左子树或右子树上,返回那颗非空的子树
        return (left != null ? left : right);
    }

}
